package com.zdb.datastructures.linkedlist;

public class JosePhuDemo {

    public static void main(String[] args) {

        CircleSingleLinkedList linkedList = new CircleSingleLinkedList();
        for (int i = 1; i < 11; i++) {
            linkedList.add(new CircleSingleLinkedList.Node(i));
        }
        linkedList.print();

        linkedList.count(5, 2, 8);
        linkedList.print();

    }
}

/**
 * 环状的单向链表
 *
 *
 */
class CircleSingleLinkedList {


    private Node curNode;

    public void add(Node node) {
        if(curNode == null) {
            curNode = node;
            curNode.next = curNode;
        } else {
            Node curNodeNext = curNode.next;
            curNode.next = node;
            node.next = curNodeNext;
            curNode = node;
        }
    }

    /**
     *
     * 从no开始数，每次步长K，最多数nums次
     * @param no 开始人
     * @param k 步长
     * @param nums 最多数多少次
     */
    public void count(int no, int k, int nums) {

        System.out.printf("从编号%d开始，步长为%d,最多循环%d次\r\n", no, k, nums);

        // 先将curNode定位到no的前一位
        Node beginNode = curNode;
        Node helperNode = curNode;
        while(helperNode.next != null && beginNode != helperNode.next) {
            if(helperNode.next.no == no) {
                break;
            } else {
                helperNode = helperNode.next;
            }
        }

        // 循环nums次，直至链表为空，步长为k
        for (int i = 0; i < nums; i++) {

            // 如果步长为1时，beforeNode会报空指针
            for (int j = 1; j < k; j++) {
                helperNode = helperNode.next;
            }
            // 删除该节点,如果当前节点只有一个了
            // curNode.next就是被删除的节点
            if(helperNode.next == helperNode) {
                curNode = null;
                break;
            } else {
                helperNode.next = helperNode.next.next;
            }
        }
        curNode = helperNode;
    }

    public void print() {

        if(curNode == null) {
            System.out.println("=== 链表为空 ===");
            return;
        }

        System.out.println("打印链表：\t");
        Node beginNode = curNode;
        System.out.print(curNode + "\t");
        while (curNode.next != beginNode) {
            System.out.print(curNode.next + "\t");
            curNode = curNode.next;
        }
        curNode = beginNode;
        System.out.println();
    }


    static class Node {

        private int no;

        private Node next;

        public Node(int no) {
            this.no = no;
        }

        public int getNo() {
            return no;
        }

        public void setNo(int no) {
            this.no = no;
        }

        @Override public String toString() {
            return "Node{" +
                    "no=" + no +
                    '}';
        }
    }
}
